Keys and Rooms
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're given a numbered set of storage bins. Bin 0 starts unsealed, and every other bin starts sealed shut.
Opening a bin reveals a list of numbers, where each number identifies another bin that becomes unsealed as a result. The same number can show up more than once, and a bin's list can even contain its own number.
Return whether every bin in the set can eventually be unsealed.
Input: rooms = [[1], [2], [3], []]
Output: True
Unsealing bin 0 reveals bin 1, which reveals bin 2, which reveals bin 3. All four bins end up unsealed.
Input: rooms = [[1, 3], [3, 0, 1], [2], []]
Output: False
Starting from bin 0 unseals bin 1 and bin 3. Bin 1's list only points back to bin 3, bin 0, and itself, so nothing new gets unsealed. Bin 2's list only mentions itself, and no other bin ever reveals it, so bin 2 stays sealed forever.
Input: rooms = [[0, 1], [2], []]
Output: True
Bin 0's list includes its own number, which changes nothing since it's already unsealed. It also reveals bin 1, which reveals bin 2.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.